package com.sx.sx1.lintcode.day717;

import java.util.*;

public class LC3663 {

    static class Solution {
        /**
         * @param edges: Edges of an undirected tree.
         * @return: Diameter of the undirected tree.
         */
        public int undirectedTreeDiameter(int[][] edges) {
            //创建图，用map表示
            Map<Integer, Set<Integer>> graph = new HashMap<>();
            for (int[] edge : edges) {
                int a = edge[0];
                int b = edge[1];
                if(!graph.containsKey(a)){
                    graph.put(a,new HashSet<>());
                }

                if(!graph.containsKey(b)){
                    graph.put(b,new HashSet<>());
                }

                graph.get(a).add(b);
                graph.get(b).add(a);
            }

            //随机从一个节点出发，BFS，最终得到一个点last，last肯定是直径的一个端点
            Queue<Integer> q = new LinkedList<>();
            Set<Integer> visited = new HashSet<>();
            int last =0;

            q.add(edges[0][0]); //从第一个元素出发吧，其实可以从数组中任意元素出发
            visited.add(edges[0][0]);

            while (!q.isEmpty()){
                int size = q.size();
                for (int i = 0; i <size ; i++) {
                    int cur = q.poll();
                    Set<Integer> nexts = graph.get(cur);
                    for (int next : nexts) {
                        if(visited.contains(next)) continue;
                        q.add(next);
                        visited.add(next);
                        last= next;
                    }
                }
            }

            //从last出发，BFS,有多少层，直径就是多少
            visited.clear();
            q.add(last);
            int ans =0;
            while (!q.isEmpty()){
                ans++;
                int size= q.size();
                for (int i = 0; i < size; i++) {
                    int cur = q.poll();
                    Set<Integer> nexts=  graph.get(cur);
                    for(int next: nexts){
                        if(visited.contains(next)) continue;
                        q.add(next);
                        visited.add(next);
                    }
                }
            }

            return ans-1;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        int[][] arr1 = {{0,1},{0,2}};
        System.out.println(obj.undirectedTreeDiameter(arr1));

        int[][] arr2 = {{0,1},{1,2},{2,3},{1,4},{4,5}};
        System.out.println(obj.undirectedTreeDiameter(arr2));
    }
}

/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
3663 · 无向树的直径
算法
中等
通过率
61%

题目
题解5
笔记
讨论
排名
记录
描述
给你一棵「 无向树 」，请你计算并返回它的「 直径 」，即这棵树上最长简单路径的 边数。

现用一个由所有 边 组成的数组 edges 来表示一棵无向树，其中 edges[i] = [u, v] 表示节点 u 和 v 之间的双向边。

树上的节点都使用 edges 中的数 {0, 1, ..., edges.length} 来作为标记，每个节点上的标记都是 唯一的。

edges 会形成一棵无向树。

0
<
=
e
d
g
e
s
.
l
e
n
g
t
h
<
1
0
4
0<=edges.length<10
4


e
d
g
e
s
[
i
]
[
0
]
!
=
e
d
g
e
s
[
i
]
[
1
]
edges[i][0]!=edges[i][1]

0
<
=
e
d
g
e
s
[
i
]
[
j
]
<
=
e
d
g
e
s
.
l
e
n
g
t
h
0<=edges[i][j]<=edges.length

样例
样例一

输入

edges = [[0,1],[0,2]]
输出

2
解释

edges 组成的无向树：
      0
     / \
    1   2
这棵树上最长的路径是 1 - 0 - 2，边数为 2。
样例二

输入

edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
输出

4
解释

edges 组成的无向树：
      1
    / | \
   0  2  4
     /  /
    3  5
这棵树上最长的路径是 3 - 2 - 1 - 4 - 5，边数为 4。
标签
相关题目

3686
N 叉树的直径
中等
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */
